The present invention relates generally to a system for reducing packet congestion for multiple devices that need to communicate over a network, such as the Internet. The subject matter of this application is related to my previously-filed U.S. application Ser. No. 10/697,103, now U.S. Pat. No. 7,339,923, entitled “Endpoint Packet Scheduling System,” filed on Oct. 31, 2003.
Ethernet and packet-switched Internet Protocol (IP) networks are systems for transmitting data between different points. These systems are known as “contention-based” systems. That is, all transmitters contend for network resources. All transmitters may transmit simultaneously. If they do, then network resources may be oversubscribed. When this happens, data may be delayed or lost, resulting in network impairment.
As shown in FIG. 1, a conventional network comprises a plurality of Local Area Network (LAN) endpoints, such as computers connected to an Ethernet LAN. The endpoints may comprise, for example, one or more IP-enabled telephones; video cameras; televisions; desktop computers; printers; or any other device that communicates over the LAN. The data may comprise real-time or quasi-realtime data, such as video flames, audio frames (voice-over-IP connections), and other types of data. The endpoints are coupled to one or more LAN switches 105, which connect the LAN to a Wide Area Network (WAN) through a router 106. When multiple endpoint devices transmit packets destined for the WAN, congestion can occur on the uplink 107 and 108.
When endpoint 101 sends packets destined for the WAN, the packets are sent through LAN switch 105, which also handles packets from other LAN endpoints. If too many packets are simultaneously transmitted by the other endpoints to LAN switch 105, LAN switch 105 may have a queue overflow, causing packets to be lost. Similarly, WAN router 106 may have a queue overflow, causing packets to be lost at that point.
The net result is that congestion due to contention among local transmitters causes data to be lost.
The word “packets” will be used to refer to datagrams in a LAN or Wide Area Network (WAN) environment. In a LAN environment, packets are sometimes called “frames.” In a packet-switched WAN environment, packet-switching devices are normally referred to as “routers.” In some systems, the LAN switching and WAN routing functions can be combined into a single device.
FIG. 2 illustrates the nature of the problem of dropped packets, which can occur in a LAN environment as well as a WAN environment. During periods where multiple endpoints are simultaneously transmitting packets on the network, the LAN switch 105 and/or WAN router 106 may become overloaded, such that some packets are discarded. This is typically caused by an internal queue in the devices becoming full and thus becoming unable to accept new packets until the outgoing packets have been removed from the queue. This creates a problem in that transmitting endpoints cannot be guaranteed that their packets will arrive, necessitating other solutions such as the use of guaranteed-delivery protocols such as Transmission Control Protocol (TCP). Such solutions may be inappropriate for broadcast video, voice over IP or other realtime applications, which cannot wait for retransmission of packets.
FIG. 2 depicts the situation where multiple packet flows create congestion and loss within an Ethernet switch. FIG. 2 shows four different flows on four separate Ethernet ports, Input A through Input D (elements 201 through 204), the resulting output flow, Output E (element 205) and the discarded frames 206. Note that Inputs A-D (elements 201 through 204) have bursts of packets that overlap one another time-wise. The utilization of each input 201-204 is within limits. That is, each input is not saturated or oversubscribed. The total utilization of each input 201-204 is also not too much data in aggregate to oversubscribe the Output E (element 205). However, because of the coincidental timing of the packet bursts on Input A through Input D, the Ethernet switch is oversubscribed. Thus packets will be lost when the Ethernet switch queue overflows lost packets, shown as discarded frames 206. Note that frames are not immediately discarded from the combined input frames. The switch uses a queue which is used to hold frames until a later transmission can occur. When concurrent bursts arrive, the queue can fill and cause frames to be discarded as illustrated in element 206.